package btree;
import static btree.BTreeNode.InsertResult;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User:咭咭熊
 * Date:2021 - 08 - 30
 * Time:10:06
 */

/***
 * 1.B-树是一棵多叉 平衡 搜索树
 * （1）多叉：节点中最多可以存放 k 个 key ,最多可以存放 c 个 child ,其中c = k + 1；
 *     节点中的key  按照有序的方式进行组织（线性结构）
 * （2）平衡：所有路径（从根到叶子）其长度均相等；
 * （3）搜索:
 *2.插入规则：
 * （1）有限进行查找，只掉叶子接地那，才能进行插入；
 * （2）插入过承诺，如果key 的数量超过上线，触发 “节点分裂”过程
 */
public class BTree {
    //B-树的根节点
    public BTreeNode root = null;
    //B-树中key的个数
    //B-树中key的个数不等于节点的个数
    public int size = 0;

    /***
     * B-树的插入
     * @return
     */
    public boolean insert(long key){
        if(insertWithoutSize(key)){
            size++;
            return true;
        }
        return false;
    }

    private boolean insertWithoutSize(long key) {
        //1.是否是空树
        if(root == null){
            //root = 构建一个包含key的节点
            root = new BTreeNode();
            root.keyList[0] = key;
            root.size = 1;
            return  true;
        }
        //2.不是空树的情况
        BTreeNode current = root;
        while (true){
            BTreeNode node = current.findKey(key);
            if(node == current){
                //key就在current节点中——插入失败；不可以重复插入key值，即插入失败
                return  false;
            }else if(node == null){
                //说明current就是叶子节点
                //说明current就是接下来要插入key的节点
                break;
            }else{
                //找到了一个孩子，并且current不是叶子
                //规则：插入必须发生在叶子节点上
                current = node;

            }
        }

        //进行key的插入
        //current 就是我们要进行 key 插入的节点
        //current此时一定是叶子
        InsertResult ret = current.insert(key);
        while (true) {
            if (ret == null) {
                //插入过程中，没有发生节点分裂，直接退出
                return true;
            }

            //说明发生了分裂
            //需要将分裂出来的key 和分裂出来的节点，插入到current。parent中
            BTreeNode parent = current.parent;
            if (parent == null) {
                //说明current是跟节点
                //即跟节点发生了分裂
                //需要一个新的跟节点，来保存分裂出来的key
                root = new BTreeNode();
                root.keyList[0] = ret.key;
                root.size = 1;
                root.childList[0] = current;
                root.childList[1] = ret.node;

                //由于原来current是跟节点，所以其parent= null
                //所以分裂出来的节点也是null
                //所以为他们设置新的父节点
                current.parent = ret.node.parent = root;
                return true;
            }
            //此时说明不是根节点分裂了；
            ret = parent.insertKeyWithChild(ret.key,ret.node);
            current = parent;
        }

    }

}

